In network environments paths are calculated between nodes using network topology information. These paths are commonly shortest paths between the nodes and the set of shortest paths from a given node to a set of destination nodes can be considered a shortest path tree. These shortest path trees can be utilized for establishing general routing between nodes or service related routing to interconnect a set of virtual network attachment points for connectivity establishment and maintenance. The determination of the paths can be based on a link based metric. As shortest path trees are added to the network the load associated with each tree can alter the metrics.
Load distribution or load spreading is a method by which breadth of connectivity is more effectively utilized and overall performance is improved in a network. Most automated load distribution and load spreading techniques deployed today, especially those in networks with a distributed control plane, operate with only a very local view, whereby these load distribution and load spreading techniques only consider the number of paths or the next hops to a given destination and do not consider the overall distribution of traffic in the network.
Equal cost multi-path (ECMP) is a common strategy for load spreading of unicast traffic in routed networks that is utilized where the decision as to how to forward a packet to a given destination can resolve to any one of multiple “equal cost” paths, which have been determined to be tied for being the shortest path when running calculations on a topology database. ECMP can be used in conjunction with most unicast routing protocols and nodes equipped with the required supporting data plane hardware, since it relies on a per hop decision that is local to a single router and assumes promiscuous receipt and forwarding of frames combined with a complete forwarding table at every intermediate node. Using ECMP at any given node in a network, the load is divided pseudo-evenly across the set of equal cost next hops. This process is implemented independently at each hop of the network where more than one next hop to a given destination exists.
In many implementations, when the presence of multiple equal cost next hops is encountered, each packet is inspected for a source of entropy such as an Internet Protocol (IP) header and a hash of header information modulo the number of equal cost next hops is used to select the next hop on which to forward the particular packet. For highly aggregated traffic, this method will on average distribute the load evenly in regular topologies (i.e., symmetric topologies) and does offer some improvement in less regular topologies.
ECMP is suitable for networks that have very large communities of interest as the traffic matrix cannot be predicted. However for networks with many small communities of interest and networks that require congruent unicast and multicast forwarding, ECMP is not a good solution, and ECMP solution can demonstrate superior load spreading properties, combined with guaranteed ordered delivery and superior operations, administration and management (OAM) coverage and capability.
In a network where congruent unicast and multicast trees are computed a tie-breaking mechanism is required to tie-break between paths of equal or near equal cost, which is different from dealing with equal cost next hops. Standard 802.1aq defines one such basic tie-breaking mechanism.